{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基本概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计算机只能识别二进制数据，而用户需要界面，不需要知道具体细节，这一过程称之为“过程抽象”（procedural abstraction）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "程序设计刚好相反：程序设计（ Programming） 是将算法编码为计算机可执行的表示法或编程语言的过程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "而算法则是程序设计中最重要的一步，算法是解决方案。算法描述的是依据代表问题实体的数据和达到预期结果的一系列步骤的问题解决方案。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "程序设计语言必须提供一种计数性的方式来表达这个过程和这些数据。为此，程序设计语言提供了控制结\n",
    "构和数据类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "控制结构使得算法的步骤能被简洁而明确地表达。数据类型把这些二进制数据翻译成我们可以理解的、在解决问题中讲得\n",
    "通的内容。这些底层的、预置的数据类型（有时也叫做原始数据类型）是算法发展的基石。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "早期，我们把对程序的抽象视为一种通过隐藏特定函数的细节让用户或用户可以在更高层次看\n",
    "问题的方法。 数据抽象（ data abstraction） 的思想与之相似。 抽象数据类型（ abstract data\n",
    "type） （ 常简写为ADT），不涉及数据、操作如何被执行，只是关于如何查看数据和许可操作的逻辑\n",
    "性描述。这意味着我们关注的只是数据代表的含义而不是最终运行的过程。通过提出这种抽象概\n",
    "念，我们实现了对数据的封装（ encapsulation） 。这种理念就是通过对执行的数据的封装，使之从\n",
    "用户视野中消失。这就叫做信息隐藏（ information hiding） 。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "抽象数据类型的执行，常被称为数据结构（ data structure） ，它需要我们用一些程序设计和原\n",
    "始数据类型来提供一个关于数据的实际展示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 时间复杂度和空间复杂度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。\n",
    "- 在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。\n",
    "- 类似于 [1]  时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。\n",
    "\n",
    "一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\\\"进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 大O表示法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当我们试图用执行时间作为独立于具体程序或计算机的度量指标去描述一个算法的效率时，确\n",
    "定这个算法所需要的操作数或步骤数显得尤为重要。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用O(n)来体现算法时间复杂度的记法被称作大O表示法,一般我们我们评估一个算法都是直接评估它的最坏的复杂度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "大O表示法O(f(n))中的f(n)的值可以为: \n",
    "\n",
    "|f(n)| 函数名|\n",
    "|--|--|\n",
    "|1 |常数函数|\n",
    "|log n| 对数函数|\n",
    "|n |线性函数|\n",
    "|n log n| 线性对数函数|\n",
    "|n²| 二次函数|\n",
    "|n³| 三次函数|\n",
    "|2^n| 指数函数|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意到当 n 很小时，函数之间不易区分，很难说谁占主导。\n",
    "然而，当 n 增大时，就能观察到明显的区别，很容易进行比较。\n",
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 大O表示法(复杂度分析)：https://blog.csdn.net/weixin_38483589/article/details/84147376\n",
    "- 01 - 大O表示法：https://blog.csdn.net/M316625387/article/details/89785602"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 线性结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "线性结构：当添加一个项目时，它就被放在这样一个位置：在之前存在的项与后来要加入的项之间。像这样的数据集合常被称为线性数据结构。\n",
    "线性结构有顺序结构和链式结构两种。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。<sup>[Re](https://baike.baidu.com/item/栈/12808149?fr=aladdin)</sup>   \n",
    "栈的“底”是有标志性的，因为存储在栈中更靠近“底”的项就是栈中储存时间最长的项。\n",
    "最新添加的项在移除项时也会第一个被移除。这种排序原则有时也称为 LIFO(last-in first-out)法，也就是“**后进先出**” 。 \n",
    "\n",
    "![栈的结构]()  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1．进栈（PUSH）算法  \n",
    "- ①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；  \n",
    "- ②置TOP=TOP+1（栈指针加1，指向进栈地址）；  \n",
    "- ③S(TOP)=X，结束（X为新进栈的元素）；  \n",
    "\n",
    "2．退栈（POP）算法  \n",
    "- ①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；  \n",
    "- ②X=S(TOP)，（退栈后的元素赋给X）：  \n",
    "- ③TOP=TOP-1，结束（栈指针减1，指向栈顶）。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈不是Python的内建数据类型，但我们可以通过以下方式来模拟栈的结构：  \n",
    "１）list\n",
    "\n",
    "２）collections.deque\n",
    "\n",
    "３）queue.LifoQueue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**使用List模拟栈(不推荐，不要重复造轮子)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 模拟顺序结构\n",
    "class Stack(object):\n",
    "\n",
    "    def __init__(self):\n",
    "     # 创建空列表实现栈\n",
    "        self.__list = []\n",
    "\n",
    "    def is_empty(self):\n",
    "    # 判断是否为空\n",
    "        return self.__list == []\n",
    "    def push(self,item):\n",
    "    # 压栈，添加元素\n",
    "        self.__list.append(item)\n",
    "\n",
    "    def pop(self):\n",
    "    # 弹栈，弹出最后压入栈的元素\n",
    "        if self.is_empty():\n",
    "            return \n",
    "        else:\n",
    "            return self.__list.pop()\n",
    "\n",
    "    def top(self): \n",
    "    # 取最后压入栈的元素\n",
    "        if self.is_empty():\n",
    "            return\n",
    "        else:\n",
    "            return self.__list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 模拟链表结构\n",
    "class Head(object):\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "class Queue(object):\n",
    "    def __init__(self):\n",
    "        #初始化节点\n",
    "        self.head = Head()\n",
    "\n",
    "    def enqueue(self, value):\n",
    "        #插入一个元素\n",
    "        newnode = Node(value)\n",
    "        p = self.head\n",
    "        if p.right:\n",
    "            #如果head节点的右边不为None\n",
    "            #说明队列中已经有元素了\n",
    "            #就执行下列的操作\n",
    "            temp = p.right\n",
    "            p.right = newnode\n",
    "            temp.next = newnode\n",
    "        else:\n",
    "            #这说明队列为空，插入第一个元素\n",
    "            p.right = newnode\n",
    "            p.left = newnode\n",
    "\n",
    "    def dequeue(self):\n",
    "        #取出一个元素\n",
    "        p = self.head\n",
    "        if p.left and (p.left == p.right):\n",
    "            #说明队列中已经有元素\n",
    "            #但是这是最后一个元素\n",
    "            temp = p.left\n",
    "            p.left = p.right = None\n",
    "            return temp.value\n",
    "        elif p.left and (p.left != p.right):\n",
    "            #说明队列中有元素，而且不止一个\n",
    "            temp = p.left\n",
    "            p.left = temp.next\n",
    "            return temp.value\n",
    "\n",
    "        else:\n",
    "            #说明队列为空\n",
    "            #抛出查询错误\n",
    "            raise LookupError('queue is empty!')\n",
    "\n",
    "    def is_empty(self):\n",
    "        if self.head.left:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "    def top(self):\n",
    "        #查询目前队列中最早入队的元素\n",
    "        if self.head.left:\n",
    "            return self.head.left.value\n",
    "        else:\n",
    "            raise LookupError('queue is empty!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**使用collections.deque实现栈**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**使用queue module实现栈**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 队列\n",
    "队列(Queue)是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。  \n",
    "最新被加入的元素必须处于队尾，在队列停留最长时间的元素处于队首。这种原则有时候叫做\n",
    "“先进先出”（ FIFO, first-in first-out） ，有时候也叫做“先到先服务”。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "顺序队列中的溢出现象：  \n",
    "- （1） \"下溢\"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。  \n",
    "- （2）\"真上溢\"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。  \n",
    "- （3）\"假上溢\"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为\"假上溢\"现象。  \n",
    "在实际使用队列时，为了使队列空间能重复使用，避免“假上溢”，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。  \n",
    "![双端队列]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "队列可以通过queue类来实现，queue可以实现以下队列方式：\n",
    "\n",
    "- Queue：FIFO 即first in first out 先进先出\n",
    "\n",
    "- LifoQueue：LIFO 即last in first out 后进先出(栈)\n",
    "\n",
    "- PriorityQueue：优先队列，级别越低，越优先  \n",
    "- deque：双边队列\n",
    "\n",
    "queue常见用法如下:\n",
    "\n",
    "|方法|作用|\n",
    "|--|--|\n",
    "|Queue.qsize()| 返回队列的大小|\n",
    "|Queue.empty() |如果队列为空，返回True,反之False|\n",
    "|Queue.full()| 如果队列满了，返回True,反之False，Queue.full 与 maxsize 大小对应|\n",
    "|Queue.get([block[, timeout]])|获取队列，timeout等待时间|\n",
    "|Queue.get_nowait() |相当于Queue.get(False)，非阻塞方法|\n",
    "|Queue.put(item) |写入队列，timeout等待时间|\n",
    "|Queue.task_done() |在完成一项工作之后，Queue.task_done()函数向任务已经完成的队列发送一个信号。每个get()调用得到一个任务，接下来task_done()调用告诉队列该任务已经处理完毕。|\n",
    "|Queue.join()| 实际上意味着等到队列为空，再执行别的操作|\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 双端队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双端队列（ deque 或 double-ended queue）与队列类似，也是一系列元素的有序组合。其两端称为队首（ front）和队尾（ rear），元素在到达两端之前始终位于双端队列中。与队列不同的是，双端队列对元素添加和删除的限制不那么严格，元素可以从两端插入，也可以从两端删除。 在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在Python中，使用queue库和[collections](https://www.cnblogs.com/brainstorming/p/7654820.html)库可以实现双端队列，具体用法后期再查。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 基本概念\n",
    "树是由节点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO 这里有上边流程图的源代码，后期研究一下怎么直接导入\n",
    "<mxGraphModel dx=\"1108\" dy=\"687\" grid=\"1\" gridSize=\"10\" guides=\"1\" tooltips=\"1\" connect=\"1\" arrows=\"1\" fold=\"1\" page=\"1\" pageScale=\"1\" pageWidth=\"827\" pageHeight=\"1169\" background=\"#ffffff\">\n",
    "  <root>\n",
    "    <mxCell id=\"0\"/>\n",
    "    <mxCell id=\"1\" parent=\"0\"/>\n",
    "    <mxCell id=\"3\" value=\"根节点(Root&lt;span style=&quot;letter-spacing: 0px&quot;&gt;)&lt;/span&gt;\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"340\" y=\"120\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"10\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"179\" y=\"360\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"12\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"271\" y=\"270\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"13\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"141\" y=\"270\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"14\" value=\"&lt;span&gt;父节点&lt;/span&gt;\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"490\" y=\"195\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"15\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"205\" y=\"195\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"17\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=1;entryY=0;exitX=0.5;exitY=1;strokeColor=#FF0000;strokeWidth=2;\" parent=\"1\" source=\"3\" target=\"15\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"270\" y=\"200\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"320\" y=\"150\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"18\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=0;entryY=0;exitX=0.5;exitY=1;\" parent=\"1\" source=\"3\" target=\"14\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"375\" y=\"180\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"258\" y=\"220\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"20\" value=\"&lt;span&gt;子节点2&lt;/span&gt;\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"555\" y=\"270\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"21\" value=\"&lt;span&gt;子节点1&lt;/span&gt;\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"425\" y=\"270\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"22\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=1;entryY=0;exitX=0.5;exitY=1;\" parent=\"1\" source=\"15\" target=\"13\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"140\" y=\"390\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"190\" y=\"340\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"23\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=0;entryY=0;exitX=0.5;exitY=1;strokeColor=#FF0000;strokeWidth=2;\" parent=\"1\" source=\"15\" target=\"12\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"240\" y=\"255\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"194\" y=\"287\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"24\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=1;entryY=0;exitX=0.5;exitY=1;\" parent=\"1\" source=\"14\" target=\"21\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"510\" y=\"245\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"471\" y=\"277\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"25\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=0;entryY=0;exitX=0.5;exitY=1;\" parent=\"1\" source=\"14\" target=\"20\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"502\" y=\"340\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"550\" y=\"372\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"26\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"310\" y=\"360\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"27\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"240\" y=\"360\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"28\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"459\" y=\"360\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"29\" value=\"叶节点\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"389\" y=\"360\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"30\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"590\" y=\"360\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"31\" value=\"\" style=\"ellipse;whiteSpace=wrap;html=1;aspect=fixed;fontStyle=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"520\" y=\"360\" width=\"50\" height=\"50\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"32\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=0.5;entryY=0;exitX=0.5;exitY=1;\" parent=\"1\" source=\"13\" target=\"10\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"100\" y=\"410\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"150\" y=\"360\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"33\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=0.5;entryY=0;exitX=0.5;exitY=1;strokeColor=#FF0000;strokeWidth=2;\" parent=\"1\" source=\"12\" target=\"27\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"176\" y=\"330\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"187\" y=\"377\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"34\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;exitX=0.5;exitY=1;entryX=0.5;entryY=0;\" parent=\"1\" source=\"12\" target=\"26\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"380\" y=\"480\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"320\" y=\"370\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"35\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=0.5;entryY=0;exitX=0.5;exitY=1;\" parent=\"1\" source=\"21\" target=\"29\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"140\" y=\"480\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"190\" y=\"430\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"36\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=0.5;entryY=0;exitX=0.5;exitY=1;\" parent=\"1\" source=\"21\" target=\"28\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"140\" y=\"480\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"190\" y=\"430\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"37\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;entryX=0.5;entryY=0;exitX=0.5;exitY=1;\" parent=\"1\" source=\"20\" target=\"31\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"140\" y=\"480\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"190\" y=\"430\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"38\" value=\"\" style=\"endArrow=classic;html=1;fontSize=12;exitX=0.5;exitY=1;entryX=0.5;entryY=0;\" parent=\"1\" source=\"20\" target=\"30\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"570\" y=\"490\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"600\" y=\"360\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"40\" value=\"\" style=\"endArrow=none;dashed=1;html=1;fontSize=12;startArrow=blockThin;startFill=1;exitX=1;exitY=0.5;entryX=0;entryY=0.5;\" parent=\"1\" source=\"3\" target=\"44\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"410\" y=\"140\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"650\" y=\"120\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"41\" value=\"\" style=\"endArrow=none;dashed=1;html=1;fontSize=12;startArrow=blockThin;startFill=1;entryX=0.02;entryY=0.833;entryPerimeter=0;\" parent=\"1\" target=\"44\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"540\" y=\"198\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"650\" y=\"120\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"44\" value=\"节点(Node)\" style=\"text;html=1;strokeColor=#000000;fillColor=#ffffff;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"580\" y=\"130\" width=\"50\" height=\"30\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"45\" value=\"\" style=\"endArrow=none;dashed=1;html=1;fontSize=12;startArrow=blockThin;startFill=1;exitX=1;exitY=0;\" parent=\"1\" source=\"20\" target=\"44\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"610\" y=\"260\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"650\" y=\"120\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"47\" value=\"\" style=\"endArrow=none;dashed=1;html=1;fontSize=12;startArrow=blockThin;startFill=1;entryX=1;entryY=0.75;\" parent=\"1\" target=\"49\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"310\" y=\"180\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"110\" y=\"170\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"49\" value=\"边(Edge)\" style=\"text;html=1;strokeColor=#000000;fillColor=#ffffff;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"120\" y=\"140\" width=\"50\" height=\"30\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"50\" value=\"\" style=\"endArrow=none;dashed=1;html=1;fontSize=12;startArrow=blockThin;startFill=1;\" parent=\"1\" target=\"49\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"200\" y=\"260\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"100\" y=\"170\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"52\" value=\"路径(Path)\" style=\"text;html=1;strokeColor=#000000;fillColor=#ffffff;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=12;\" parent=\"1\" vertex=\"1\">\n",
    "      <mxGeometry x=\"335\" y=\"205\" width=\"50\" height=\"45\" as=\"geometry\"/>\n",
    "    </mxCell>\n",
    "    <mxCell id=\"54\" value=\"\" style=\"endArrow=none;dashed=1;html=1;fontSize=12;startArrow=blockThin;startFill=1;\" parent=\"1\" edge=\"1\">\n",
    "      <mxGeometry width=\"50\" height=\"50\" relative=\"1\" as=\"geometry\">\n",
    "        <mxPoint x=\"270\" y=\"250\" as=\"sourcePoint\"/>\n",
    "        <mxPoint x=\"330\" y=\"220\" as=\"targetPoint\"/>\n",
    "      </mxGeometry>\n",
    "    </mxCell>\n",
    "  </root>\n",
    "</mxGraphModel>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上图，理解一下树的基本相关概念：  \n",
    "- **节点（ Node）**：节点（ Node）是树的基本构成部分。它可以有其他专属的名称，我们称之为“键（ key） ”。 一个节点可能有更多的信息，我们称之为“负载（ payload） ”。 尽管负载信息和树的许多算法并不直接相关，但是它对于树的应用至关重要。\n",
    "- **边（ Edge）**：边（ Edge）也是另一个树的基本构成部分。边连接两个节点，并表示它们之间存在联系。每个节点（ 除了根节点） 都有且只有一条与其他节点相连的入边（指向该节点的边），每个节点可能有许多条出边（从该节点指向其他节点的边）。\n",
    "- **根节点（ Root）**：根节点是树中唯一一个没有入边的节点。\n",
    "- **路径（ Path）**：路径是由边连接起来的节点的有序排列。\n",
    "- **子节点集（ Children）**：当一个节点的入边来自另一个节点时，我们称前者是后者的子节点，同一个节点的所有子节点构成子节点集。\n",
    "- **父节点（ Parent）**：一个节点是它的出边所连接的所有节点的父节点。\n",
    "- **兄弟节点（ Sibling）**：同一个节点的所有子节点互为兄弟节点。\n",
    "- **子树（ Subtree）**：子树是一个父节点的某个子节点的所有边和后代节点所构成的集合。\n",
    "- **叶节点（ Leaf Node）**：没有子节点的节点成为称为叶节点。\n",
    "- **层数（ Level）**：一个节点的层数是指从根节点到该节点的路径中的边的数目。定义根节点的层数为 0。\n",
    "- **高度（ Height）**：树的高度等于所有节点的层数的最大值。\n",
    "- **节点的度**：一个节点含有的子树的个数称为该节点的度；\n",
    "- **树的度**：一棵树中，最大的节点的度称为树的度；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树的种类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "树的种类：  \n",
    "- 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；使用较少\n",
    "- 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；一般情况下都讨论有序树、\n",
    "    - 二叉树：每个节点最多含有两个子树的树称为二叉树；\n",
    "        - 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;\n",
    "        - 堆(二叉堆)：二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。\n",
    "        - 排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）：一个节点的左子节点的数小于该节点，右子节点的数大于或等于该父节点\n",
    "        - 霍夫曼树（用于信息编码）<sup>[Re](https://blog.csdn.net/ZP_icenow/article/details/81041215)</sup>：霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。\n",
    "        - 平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；     \n",
    "            - AVL树(自平衡二叉查找树)：任一节点的左子树深度和右子树深度相差不超过1。我们用平衡因子(Balance(p)= heigth(p的左子树) - height（p的右子树）)衡量这种差异,在进行AVL树的插入和删除操作时，当平衡因子=2时，就要调整节点的位置，使其满足AVL树的定义。\n",
    "            - 红黑树：它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。节点分红色或黑色，根节点是黑色，每个叶节点（NIL节点，空节点）是黑色的。每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)， 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。\n",
    "    - 23树：2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。\n",
    "    - 234树：2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构，可以保证在O(lgn)的时间内完成查找、插入和删除操作。（详见参考文献）\n",
    "    - B树：B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。根节点至少有两个子节点。每个节点有M-1个key，并且以升序排列。位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间。其它节点至少有M/2个子节点。\n",
    "    - B+树：B+树是对B树的一种变形树，它与B树的差异在于：有k个子结点的结点必然有k个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。(B树和B+广泛应用于文件存储系统以及数据库系统中)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|名称\t|简介\t|旋转规则\t|插入\t|删除\t|查找\t|使用场景|\n",
    "|-|-|-|-|-|-|-|\n",
    "|AVL树\t|高度平衡二叉查找树，左右子树高度差不超过1\t|不满足高度平衡就旋转直到平衡\t|O(logN)\t|O(logN)，但最坏旋转logN次\t|O(logN)\t|查找多，数据变动少|\n",
    "|红黑树\t|根黑叶黑，红带两黑。非叶到叶黑树相等，且路径相差不会超过1倍，非高度平衡\t|旋转次数较AVL少\t|较AVL差一些（非高度平衡）\t|较AVL好，最多旋转两次\t|较AVL差一些（非高度平衡）\t|数据变动多。Java TreeSet ConcurrentHashMap|\n",
    "|B树\t|多路查找树，分支多、树矮，磁盘IO少。n个子树节点包含n+1个关键字\t|-\t|O(logN),可能分裂\t|O(logN)|\tO(logN)\t|B树相较B+树可把HotData放在Non-leaf以快速查找|\n",
    "|B+树\t|多路查找树，分支多、树矮，磁盘IO少。n个子树节点包含n个索引关键字，数据存叶节点\t|-\t|O(logN),可能分裂\t|O(logN)\t|O(logN)\t|快速遍历数据(二分查找)。文件系统、索引|\n",
    "|2-3-4树\t|节点最多有4个子节点和3个数据项;叶节点同层;节点key值有序|\t-\t|-\t|-\t|-\t|内存查找|\n",
    "|Trie树\t|字典树，不同字符串的相同前缀共享保存一份\t|-\t|O(len(word)|\t-\t|O(len(word))\t|前缀匹配，统计和排序大量的字符串|\n",
    "|LSM树\t|延迟、批量更新（滚动合并）；写内存效率高；读效率略低\t|-\t|远高于B树\t|墓碑机制\t|稍差\t|LSM树适用于长期具有高频次数据更新而查询较少的场景。|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树的存储\n",
    "- 顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。\n",
    "- 链式存储："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 二叉树的遍历\n",
    "- 概念：按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。\n",
    "- 分类：\n",
    "    - 深度优先遍历，根据访问次序的不同可以分为三类(速记：根据根节点访问次序记忆，做一直在)：\n",
    "        - 前序遍历(preorder)：在前序遍历中，我们先访问根节点，然后递归地前序遍历访问左子树，再递归地前序遍历访问右子树。访问次序：中左右，如下图1\n",
    "        - 中序遍历(inorder)：在中序遍历中，我们递归地中序遍历访问左子树，然后访问根节点，最后再递归地中序遍历访问右子树。访问次序：左中右，如下图2\n",
    "        - 后序遍历(postorder)：在后序遍历中，我们先递归地后序遍历访问左子树和右子树，最后访问根节点。访问次序：左右中，如下图3\n",
    "    - 广度优先遍历：也叫层序遍历，一层一层的遍历。如下图4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"center\">\n",
    "<img src=\"\" >\n",
    "\n",
    "<img src=\"\" >\n",
    "\n",
    "<img src=\"\" >\n",
    "<img src=\"\">\n",
    "\n",
    " </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 树的Python实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T11:59:04.108366Z",
     "iopub.status.busy": "2020-08-06T11:59:04.104378Z",
     "iopub.status.idle": "2020-08-06T11:59:04.195172Z",
     "shell.execute_reply": "2020-08-06T11:59:04.191220Z",
     "shell.execute_reply.started": "2020-08-06T11:59:04.107369Z"
    }
   },
   "outputs": [],
   "source": [
    "from graphviz import Digraph\n",
    "import uuid\n",
    "from random import sample\n",
    "\n",
    "# 二叉树类\n",
    "class BTree(object):\n",
    "\n",
    "    # 初始化\n",
    "    def __init__(self, data=None, left=None, right=None):\n",
    "        self.data = data    # 数据域\n",
    "        self.left = left    # 左子树\n",
    "        self.right = right  # 右子树\n",
    "        self.dot = Digraph(comment='Binary Tree')\n",
    "\n",
    "    # 前序遍历\n",
    "    def preorder(self):\n",
    "\n",
    "        if self.data is not None:\n",
    "            print(self.data, end=' ')\n",
    "        if self.left is not None:\n",
    "            self.left.preorder()\n",
    "        if self.right is not None:\n",
    "            self.right.preorder()\n",
    "\n",
    "    # 中序遍历\n",
    "    def inorder(self):\n",
    "\n",
    "        if self.left is not None:\n",
    "            self.left.inorder()\n",
    "        if self.data is not None:\n",
    "            print(self.data, end=' ')\n",
    "        if self.right is not None:\n",
    "            self.right.inorder()\n",
    "\n",
    "    # 后序遍历\n",
    "    def postorder(self):\n",
    "\n",
    "        if self.left is not None:\n",
    "            self.left.postorder()\n",
    "        if self.right is not None:\n",
    "            self.right.postorder()\n",
    "        if self.data is not None:\n",
    "            print(self.data, end=' ')\n",
    "\n",
    "    # 层序遍历\n",
    "    def levelorder(self):\n",
    "\n",
    "        # 返回某个节点的左孩子\n",
    "        def LChild_Of_Node(node):\n",
    "            return node.left if node.left is not None else None\n",
    "        # 返回某个节点的右孩子\n",
    "        def RChild_Of_Node(node):\n",
    "            return node.right if node.right is not None else None\n",
    "\n",
    "        # 层序遍历列表\n",
    "        level_order = []\n",
    "        # 是否添加根节点中的数据\n",
    "        if self.data is not None:\n",
    "            level_order.append([self])\n",
    "\n",
    "        # 二叉树的高度\n",
    "        height = self.height()\n",
    "        if height >= 1:\n",
    "            # 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据\n",
    "            for _ in range(2, height + 1):\n",
    "                level = []  # 该层的节点\n",
    "                for node in level_order[-1]:\n",
    "                    # 如果左孩子非空，则添加左孩子\n",
    "                    if LChild_Of_Node(node):\n",
    "                        level.append(LChild_Of_Node(node))\n",
    "                    # 如果右孩子非空，则添加右孩子\n",
    "                    if RChild_Of_Node(node):\n",
    "                        level.append(RChild_Of_Node(node))\n",
    "                # 如果该层非空，则添加该层\n",
    "                if level:\n",
    "                    level_order.append(level)\n",
    "\n",
    "            # 取出每层中的数据\n",
    "            for i in range(0, height):  # 层数\n",
    "                for index in range(len(level_order[i])):\n",
    "                    level_order[i][index] = level_order[i][index].data\n",
    "\n",
    "        return level_order\n",
    "\n",
    "    # 二叉树的高度\n",
    "    def height(self):\n",
    "        # 空的树高度为0, 只有root节点的树高度为1\n",
    "        if self.data is None:\n",
    "            return 0\n",
    "        elif self.left is None and self.right is None:\n",
    "            return 1\n",
    "        elif self.left is None and self.right is not None:\n",
    "            return 1 + self.right.height()\n",
    "        elif self.left is not None and self.right is None:\n",
    "            return 1 + self.left.height()\n",
    "        else:\n",
    "            return 1 + max(self.left.height(), self.right.height())\n",
    "\n",
    "    # 二叉树的叶子节点\n",
    "    def leaves(self):\n",
    "\n",
    "        if self.data is None:\n",
    "            return None\n",
    "        elif self.left is None and self.right is None:\n",
    "            print(self.data, end=' ')\n",
    "        elif self.left is None and self.right is not None:\n",
    "            self.right.leaves()\n",
    "        elif self.right is None and self.left is not None:\n",
    "            self.left.leaves()\n",
    "        else:\n",
    "            self.left.leaves()\n",
    "            self.right.leaves()\n",
    "\n",
    "    # 利用Graphviz实现二叉树的可视化\n",
    "    def print_tree(self, save_path='./Binary_Tree.gv', label=False):\n",
    "\n",
    "        # colors for labels of nodes\n",
    "        colors = ['skyblue', 'tomato', 'orange', 'purple', 'green', 'yellow', 'pink', 'red']\n",
    "\n",
    "        # 绘制以某个节点为根节点的二叉树\n",
    "        def print_node(node, node_tag):\n",
    "            # 节点颜色\n",
    "            color = sample(colors,1)[0]\n",
    "            if node.left is not None:\n",
    "                left_tag = str(uuid.uuid1())            # 左节点的数据\n",
    "                self.dot.node(left_tag, str(node.left.data), style='filled', color=color)    # 左节点\n",
    "                label_string = 'L' if label else ''    # 是否在连接线上写上标签，表明为左子树\n",
    "                self.dot.edge(node_tag, left_tag, label=label_string)   # 左节点与其父节点的连线\n",
    "                print_node(node.left, left_tag)\n",
    "\n",
    "            if node.right is not None:\n",
    "                right_tag = str(uuid.uuid1())\n",
    "                self.dot.node(right_tag, str(node.right.data), style='filled', color=color)\n",
    "                label_string = 'R' if label else ''  # 是否在连接线上写上标签，表明为右子树\n",
    "                self.dot.edge(node_tag, right_tag, label=label_string)\n",
    "                print_node(node.right, right_tag)\n",
    "\n",
    "        # 如果树非空\n",
    "        if self.data is not None:\n",
    "            root_tag = str(uuid.uuid1())                # 根节点标签\n",
    "            self.dot.node(root_tag, str(self.data), style='filled', color=sample(colors,1)[0])     # 创建根节点\n",
    "            print_node(self, root_tag)\n",
    "\n",
    "        self.dot.render(save_path)                              # 保存文件为指定文件"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T12:37:05.758304Z",
     "iopub.status.busy": "2020-08-06T12:37:05.757307Z",
     "iopub.status.idle": "2020-08-06T12:37:06.140604Z",
     "shell.execute_reply": "2020-08-06T12:37:06.137614Z",
     "shell.execute_reply.started": "2020-08-06T12:37:05.758304Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "先序遍历为:\n",
      "18 7 3 4 11 88 1 3 6 2 4 \n",
      "中序遍历为:\n",
      "3 7 4 18 1 88 3 11 2 6 4 \n",
      "后序遍历为:\n",
      "3 4 7 1 3 88 2 4 6 11 18 \n",
      "层序遍历为:\n",
      "[[18], [7, 11], [3, 4, 88, 6], [1, 3, 2, 4]]\n",
      "\n",
      "树的高度为4.\n",
      "叶子节点为：\n",
      "3 4 1 3 2 4 \n"
     ]
    }
   ],
   "source": [
    "# from Binary_Tree import BTree\n",
    "\n",
    "# 构造二叉树, BOTTOM-UP METHOD\n",
    "right_tree = BTree(6)\n",
    "right_tree.left = BTree(2)\n",
    "right_tree.right = BTree(4)\n",
    "\n",
    "left_tree = BTree(88)\n",
    "left_tree.left = BTree(1)\n",
    "left_tree.right = BTree(3)\n",
    "\n",
    "tree = BTree(11)\n",
    "tree.left = left_tree\n",
    "tree.right = right_tree\n",
    "\n",
    "left_tree = BTree(7)\n",
    "left_tree.left = BTree(3)\n",
    "left_tree.right = BTree(4)\n",
    "\n",
    "right_tree = tree # 增加新的变量\n",
    "tree = BTree(18)\n",
    "tree.left = left_tree\n",
    "tree.right = right_tree\n",
    "\n",
    "print('先序遍历为:')\n",
    "tree.preorder()\n",
    "print()\n",
    "\n",
    "print('中序遍历为:')\n",
    "tree.inorder()\n",
    "print()\n",
    "\n",
    "print('后序遍历为:')\n",
    "tree.postorder()\n",
    "print()\n",
    "\n",
    "print('层序遍历为:')\n",
    "level_order = tree.levelorder()\n",
    "print(level_order)\n",
    "print()\n",
    "\n",
    "height = tree.height()\n",
    "print('树的高度为%s.' % height)\n",
    "\n",
    "print('叶子节点为：')\n",
    "tree.leaves()\n",
    "print()\n",
    "\n",
    "# 利用Graphviz进行二叉树的可视化\n",
    "tree.print_tree(save_path='./99-Cache/BTree.gv', label=True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T11:59:07.556164Z",
     "iopub.status.busy": "2020-08-06T11:59:07.555171Z",
     "iopub.status.idle": "2020-08-06T11:59:07.609024Z",
     "shell.execute_reply": "2020-08-06T11:59:07.606031Z",
     "shell.execute_reply.started": "2020-08-06T11:59:07.556164Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "先序遍历为:\n",
      "A B D H P Q I R S E J T U K V W C F L X Y M Z G N O \n",
      "\n",
      "树的高度为5.\n",
      "\n",
      "层序遍历为:\n",
      "[['A'], ['B', 'C'], ['D', 'E', 'F', 'G'], ['H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'], ['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']]\n",
      "\n",
      "叶子节点为：\n",
      "P Q R S T U V W X Y Z N O \n"
     ]
    }
   ],
   "source": [
    "# 利用列表构造二叉树\n",
    "# 列表中至少有一个元素\n",
    "def create_BTree_By_List(array):\n",
    "\n",
    "    i = 1\n",
    "    # 将原数组拆成层次遍历的数组，每一项都储存这一层所有的节点的数据\n",
    "    level_order = []\n",
    "    sum = 1\n",
    "\n",
    "    while sum < len(array):\n",
    "        level_order.append(array[i-1:2*i-1])\n",
    "        i *= 2\n",
    "        sum += i\n",
    "    level_order.append(array[i-1:])\n",
    "    # print(level_order)\n",
    "\n",
    "    # BTree_list: 这一层所有的节点组成的列表\n",
    "    # forword_level: 上一层节点的数据组成的列表\n",
    "    def Create_BTree_One_Step_Up(BTree_list, forword_level):\n",
    "\n",
    "        new_BTree_list = []\n",
    "        i = 0\n",
    "        for elem in forword_level:\n",
    "            root = BTree(elem)\n",
    "            if 2*i < len(BTree_list):\n",
    "                root.left = BTree_list[2*i]\n",
    "            if 2*i+1 < len(BTree_list):\n",
    "                root.right = BTree_list[2*i+1]\n",
    "            new_BTree_list.append(root)\n",
    "            i += 1\n",
    "\n",
    "        return new_BTree_list\n",
    "\n",
    "    # 如果只有一个节点\n",
    "    if len(level_order) == 1:\n",
    "        return BTree(level_order[0][0])\n",
    "    else: # 二叉树的层数大于1\n",
    "\n",
    "        # 创建最后一层的节点列表\n",
    "        BTree_list = [BTree(elem) for elem in level_order[-1]]\n",
    "\n",
    "        # 从下往上，逐层创建二叉树\n",
    "        for i in range(len(level_order)-2, -1, -1):\n",
    "            BTree_list = Create_BTree_One_Step_Up(BTree_list, level_order[i])\n",
    "\n",
    "        return BTree_list[0]\n",
    "\n",
    "#array = list(range(1,19))\n",
    "array = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "tree = create_BTree_By_List(array)\n",
    "\n",
    "print('先序遍历为:')\n",
    "tree.preorder()\n",
    "print()\n",
    "\n",
    "height = tree.height()\n",
    "print('\\n树的高度为%s.\\n'%height)\n",
    "\n",
    "print('层序遍历为:')\n",
    "level_order = tree.levelorder()\n",
    "print(level_order)\n",
    "print()\n",
    "\n",
    "print('叶子节点为：')\n",
    "tree.leaves()\n",
    "print()\n",
    "# tree.print_tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T12:04:55.661984Z",
     "iopub.status.busy": "2020-08-06T12:04:55.660476Z",
     "iopub.status.idle": "2020-08-06T12:04:56.070400Z",
     "shell.execute_reply": "2020-08-06T12:04:56.066407Z",
     "shell.execute_reply.started": "2020-08-06T12:04:55.661984Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.28.0 (20110507.0327)\r\n",
       " -->\r\n",
       "<!-- Title: hello Pages: 1 -->\r\n",
       "<svg width=\"76pt\" height=\"116pt\"\r\n",
       " viewBox=\"0.00 0.00 76.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph1\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\r\n",
       "<title>hello</title>\r\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-112 73,-112 73,5 -4,5\"/>\r\n",
       "<!-- Hello -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>Hello</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"34\" cy=\"-90\" rx=\"29.3479\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"34\" y=\"-86.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">Hello</text>\r\n",
       "</g>\r\n",
       "<!-- World -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>World</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"34\" cy=\"-18\" rx=\"34.1708\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"34\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">World</text>\r\n",
       "</g>\r\n",
       "<!-- Hello&#45;&#45;World -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>Hello&#45;&#45;World</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M34,-71.6966C34,-60.8463 34,-46.9167 34,-36.1043\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x253703592c8>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "h = Graph('hello', format='svg')\n",
    "h.edge('Hello', 'World')\n",
    "# print(h.pipe().decode('utf-8'))\n",
    "h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T12:38:39.972000Z",
     "iopub.status.busy": "2020-08-06T12:38:39.970011Z",
     "iopub.status.idle": "2020-08-06T12:38:40.350179Z",
     "shell.execute_reply": "2020-08-06T12:38:40.342199Z",
     "shell.execute_reply.started": "2020-08-06T12:38:39.972000Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.28.0 (20110507.0327)\r\n",
       " -->\r\n",
       "<!-- Title: parent Pages: 1 -->\r\n",
       "<svg width=\"141pt\" height=\"206pt\"\r\n",
       " viewBox=\"0.00 0.00 141.00 206.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph1\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 202)\">\r\n",
       "<title>parent</title>\r\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-202 138,-202 138,5 -4,5\"/>\r\n",
       "<!-- spam -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>spam</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"30\" cy=\"-180\" rx=\"30.3206\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"30\" y=\"-176.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">spam</text>\r\n",
       "</g>\r\n",
       "<!-- eggs -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>eggs</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"30\" cy=\"-106\" rx=\"26.949\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"30\" y=\"-102.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">eggs</text>\r\n",
       "</g>\r\n",
       "<!-- spam&#45;&#45;eggs -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>spam&#45;&#45;eggs</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M30,-161.937C30,-150.626 30,-135.828 30,-124.441\"/>\r\n",
       "</g>\r\n",
       "<!-- foo -->\r\n",
       "<g id=\"node5\" class=\"node\"><title>foo</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"133,-198 79,-198 79,-162 133,-162 133,-198\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"106\" y=\"-176.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">foo</text>\r\n",
       "</g>\r\n",
       "<!-- bar -->\r\n",
       "<g id=\"node7\" class=\"node\"><title>bar</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"133,-124 79,-124 79,-88 133,-88 133,-124\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"106\" y=\"-102.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">bar</text>\r\n",
       "</g>\r\n",
       "<!-- foo&#45;&#45;bar -->\r\n",
       "<g id=\"edge5\" class=\"edge\"><title>foo&#45;&#45;bar</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M106,-161.937C106,-150.626 106,-135.828 106,-124.441\"/>\r\n",
       "</g>\r\n",
       "<!-- bar1 -->\r\n",
       "<g id=\"node9\" class=\"node\"><title>bar1</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"133,-36 79,-36 79,-0 133,-0 133,-36\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"106\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">bar1</text>\r\n",
       "</g>\r\n",
       "<!-- bar&#45;&#45;bar1 -->\r\n",
       "<g id=\"edge7\" class=\"edge\"><title>bar&#45;&#45;bar1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M98.8582,-87.8466C96.8743,-82.257 94.9927,-75.956 94,-70 92.8309,-62.9856 92.8309,-61.0144 94,-54 94.9927,-48.044 96.8743,-41.743 98.8582,-36.1534\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"97.5\" y=\"-58.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">3</text>\r\n",
       "</g>\r\n",
       "<!-- bar1&#45;&#45;bar -->\r\n",
       "<g id=\"edge9\" class=\"edge\"><title>bar1&#45;&#45;bar</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M106,-36.084C106,-51.009 106,-72.5778 106,-87.5966\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"109.5\" y=\"-58.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">4</text>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x253729cd388>"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = Graph(name='parent')\n",
    "p.edge('spam', 'eggs')\n",
    "\n",
    "with p.subgraph(name='child', node_attr={'shape': 'box'}) as c:\n",
    "   c.edge('foo', 'bar')\n",
    "   c.edge('bar', 'bar1','3')\n",
    "   c.edge('bar1', 'bar','4')\n",
    "p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Python学习笔记——树与树算法：https://blog.csdn.net/tichimi3375/article/details/81702179\n",
    "- 用Python实现数据结构之树：https://www.cnblogs.com/sfencs-hcy/p/10341449.html\n",
    "- 多路查找树（B树）：https://blog.csdn.net/u012507032/article/details/72453271\n",
    "- 【数据结构】有序树和无序树的区别：https://blog.csdn.net/qq_30594349/article/details/75546766\n",
    "- 二叉树的四种遍历方式：https://www.cnblogs.com/du001011/p/11229170.html\n",
    "- 数据结构-常用树总结：https://blog.csdn.net/baichoufei90/article/details/84788524\n",
    "- 红黑树之 原理和算法详细介绍：https://www.cnblogs.com/aspirant/p/9084199.html\n",
    "- 各种二叉树的介绍：https://www.cnblogs.com/aspirant/p/9019396.html\n",
    "- 234树到红黑树：https://blog.csdn.net/asdfsadfasdfsa/article/details/86500552\n",
    "- 【经典数据结构】B树与B+树的解释：https://www.cnblogs.com/makai/p/10861296.html\n",
    "- MySQL索引背后的数据结构及算法原理:http://blog.codinglabs.org/articles/theory-of-mysql-index.html\n",
    "- B+树遍历与查找：https://blog.csdn.net/XiaoGong1688/article/details/100150759\n",
    "- 二叉树的Python实现：https://www.jianshu.com/p/9503238394df\n",
    "- python-graphviz图数据可视化入门：https://mlln.cn/2018/09/25/python-graphviz图数据可视化入门/#undefined\n",
    "- 使用python库--Graphviz为论文画出漂亮的示意图：https://zhuanlan.zhihu.com/p/55836821"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "相关概念：\n",
    "- **节点（Node）**：是图的基础部分。它具有名称标识“key”。顶点也可以有附加的信息项“playload”。\n",
    "- **边（Edge）**：边（也称“弧 arc”）是图的另一个基础组成部分。 如果一条边连接两个顶点，则表示两者具有联系。边可以是单向的，也可以是双向的。如果一个图中的边都是单向的，我们就说这个图是“有向图directed graph/digraph”。\n",
    "- **权重（Weight）**：为了表达从一个顶点到另一个顶点的“代价”，可以给边赋权。\n",
    "- **路径 （Path）**：图中的路径，是由边依次连接起来的顶点序列。\n",
    "- **圈（Cycle）**：有向图里的圈是首尾顶点相同的路径。没有圈的图称为“无圈图 acyclic graph”，没有圈的有向图称为“有向无圈图 directed acyclic graph 或 DAG”。 \n",
    "\n",
    "上图中的集合可以表示为：E={(v0,v1,5),(v1,v2,4),(v2,v3,9),(v3,v4,7),(v4,v0,1),(v0,v5,2),(v5,v4,8),(v3,v5,3),(v5,v2,1)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码描述"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "理论上，图就是一堆顶点和边对象而已，但是怎么在代码中来描述呢？有两种主要的方法：**邻接列表和邻接矩阵**。  \n",
    "- **邻接列表**：\n",
    "    - 在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。比如，如果顶点A 有一条边到B、C和D，那么A的列表中会有3条边。  \n",
    "    - 邻接列表只描述了指向外部的边。A 有一条边到B，但是B没有边到A，所以 A没有出现在B的邻接列表中。查找两个顶点之间的边或者权重会比较费时，因为遍历邻接列表直到找到为止。\n",
    "\n",
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **邻接矩阵**：在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如，如果从顶点A到顶点B有一条权重为 5.6 的边，那么矩阵中第A行第B列的位置的元素值应该是5.6,往这个图中添加顶点的成本非常昂贵，因为新的矩阵结果必须重新按照新的行/列创建，然后将已有的数据复制到新的矩阵中。\n",
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|操作|邻接列表|邻接矩阵|\n",
    "|--|--|--|\n",
    "|存储空间|O(V + E)|O(V^2)|\n",
    "|添加顶点|O(1)|O(V^2)|\n",
    "|添加边|O(1)|O(1)|\n",
    "|检查相邻性|O(V)|O(1)|\n",
    "\n",
    "“检查相邻性” 是指对于给定的顶点，尝试确定它是否是另一个顶点的邻居。在邻接列表中检查相邻性的时间复杂度是O(V)，因为最坏的情况是一个顶点与每一个顶点都相连。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献\n",
    "- 数据结构：图（Graph）：https://www.jianshu.com/p/bce71b2bdbc8\n",
    "- 漫画：为什么你需要了解数据结构中的图？:https://baijiahao.baidu.com/s?id=1629054934725051961&wfr=spider&for=pc\n",
    "- 数据结构：图结构的实现：https://blog.csdn.net/zhaozigu123/article/details/79283616"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 状态机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用来梳理逻辑的，通过代码来实现，Python有专门的库，后边用到多学习一下。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 有限状态机(Python)：https://www.cnblogs.com/21207-iHome/p/6085334.html\n",
    "- 有限状态机FSM详解（一）：https://blog.csdn.net/benjonc/article/details/79870947?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.add_param_isCf&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.add_param_isCf\n",
    "- Python实现状态机：https://blog.csdn.net/StoryMonster/article/details/99443480\n",
    "- 史上最详细的用python写2048小游戏教程（一）：有限状态机：https://zhuanlan.zhihu.com/p/32743628\n",
    "- 史上最详细的用python写2048小游戏教程（二）：大功告成：https://zhuanlan.zhihu.com/p/32754266\n",
    "- 用python实现有限状态自动机FSM：http://www.voidcn.com/search/pmuiex\n",
    "- 状态机：https://blog.csdn.net/iron_lzn/article/details/86542849\n",
    "- 什么是状态机？：https://zhuanlan.zhihu.com/p/47434856"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-06T12:44:53.786100Z",
     "iopub.status.busy": "2020-08-06T12:44:53.785102Z",
     "iopub.status.idle": "2020-08-06T12:44:53.810242Z",
     "shell.execute_reply": "2020-08-06T12:44:53.807057Z",
     "shell.execute_reply.started": "2020-08-06T12:44:53.786100Z"
    }
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "from time import sleep\n",
    " \n",
    "__author__ = 'admin'\n",
    " \n",
    "'''\n",
    "    23种设计模式之状态模式：有限状态机\n",
    "    下面介绍了灯的三种状态：\n",
    "    1.开着\n",
    "    2.灭着\n",
    "    3.坏了\n",
    "    其中\"坏了\"的状态下，若是修好了，必然进入灭着的状态\n",
    "'''\n",
    " \n",
    "#   Light类\n",
    "class Light(object):\n",
    "    def __init__(self, name):\n",
    "        self.name = name\n",
    "        self.state = \"\"\n",
    "        self.fsm = None\n",
    " \n",
    "    #   开灯方法\n",
    "    def lightOn(self):\n",
    "        #   打印语句代替行为\n",
    "        print(\"灯亮着[%s]\" % self.name)\n",
    " \n",
    "    #   关灯方法\n",
    "    def lightOff(self):\n",
    "        print(\"灯灭着[%s]\" % self.name)\n",
    " \n",
    "    #   坏灯方法\n",
    "    def lightBroken(self):\n",
    "        print(\"灯坏了[%s]\" % self.name)\n",
    " \n",
    "    #   绑定状态机\n",
    "    def bind(self, state, fsm):\n",
    "        self.state = state\n",
    "        self.fsm = fsm\n",
    " \n",
    " \n",
    "# 定义状态\n",
    "class State(object):\n",
    "    def exec(self, obj):\n",
    "        pass\n",
    " \n",
    "    def exit(self, obj):\n",
    "        pass\n",
    " \n",
    " \n",
    "# 定义开灯状态，继承State(这里就是写进入该状态时该干那些事情，退出该状态时该干那些事情)\n",
    "class OnState(State):\n",
    "    #   进入还状态无非就是，将灯做打开操作\n",
    "    def exec(self, obj):\n",
    "        obj.lightOn()\n",
    " \n",
    "    #   退出该状态，无非就是，将灯做关闭操作\n",
    "    def exit(self, obj):\n",
    "        obj.lightOff()\n",
    " \n",
    " \n",
    "# 定义关灯状态，继承State\n",
    "class OffState(State):\n",
    "    def exec(self, obj):\n",
    "        obj.lightOff()\n",
    " \n",
    "    def exit(self, obj):\n",
    "        obj.lightOn()\n",
    " \n",
    " \n",
    "# 定义坏灯状态，继承State\n",
    "class BrokenState(State):\n",
    "    def exec(self, obj):\n",
    "        obj.lightBroken()\n",
    " \n",
    "    def exit(self, obj):\n",
    "        obj.lightOff()\n",
    " \n",
    " \n",
    "#   状态机管理器，这里主要做一些转换状态的操作\n",
    "class StateMachine(object):\n",
    "    def __init__(self):\n",
    "        #   指明信号和各状态的对应关系\n",
    "        self.states = {0: OnState(), 1: OffState(), 2: BrokenState()}\n",
    " \n",
    "    #   通过给定的state返回其对应的状态对象\n",
    "    def getFsm(self, state):\n",
    "        return self.states[state]\n",
    " \n",
    "    #   切换对象的状态\n",
    "    def changeState(self, NewState, objs):\n",
    "        for obj in objs:\n",
    "            #   如果新产生的信号和对象原本的执行状态对应的信号一致的话\n",
    "            if NewState == obj.state:\n",
    "                #   保持原状态\n",
    "                fsm = self.getFsm(obj.state)\n",
    "                fsm.exec(obj)\n",
    "            else:\n",
    "                #   先退出旧状态\n",
    "                old_fsm = self.getFsm(obj.state)\n",
    "                old_fsm.exit(obj)\n",
    "                #   执行新状态\n",
    "                obj.state = NewState\n",
    "                new_fsm = self.getFsm(NewState)\n",
    "                new_fsm.exec(obj)\n",
    " \n",
    " \n",
    "def run():\n",
    "    sm = StateMachine()\n",
    "    lights = []\n",
    "    names = ['red', 'green', 'yellow']\n",
    "    #   对象的制造机\n",
    "    for i in range(1):\n",
    "        l = Light(names[i])\n",
    "        l.bind(0, sm.getFsm(0))\n",
    "        lights.append(l)\n",
    "    while True:\n",
    "        #   生成新的信号\n",
    "        state = randint(0, 2)\n",
    "        sm.changeState(state, lights)\n",
    "        sleep(2)\n",
    "run()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "toc-autonumbering": true
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
